CS 5010: Problem Set 7

Out: Monday, February 29, 2016

Due: Monday, March 14, 2016 at 5pm.

The goal of this problem set is to give you practice using context arguments and invariants.

Remember that you must follow the design recipe, and write invariants (as WHERE clauses) whenever an argument represents context information.

You must use DrScheme's HtDP Intermediate Student Language with Lambda. Use list abstractions like filter, fold, and map whenever they are helpful. As before, you will be penalized for failing to use these when they are "obviously" applicable.

Not everything on this problem set requires the use of invariants; some may only require generalization. Part of your task is to figure out when you need an invariant and when you do not. Remember, it is the purpose statement that determines whether or not you need to state an invariant.

Remember you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, strategies, code, and tests. Be sure to sync your work and fill out a Work Session Report at the end of every work session. Use the Work Session Report for PS07.

As usual, the rubric for grading is here.

Required Exercises

This problem set contains two separate problems. The first problem repeats the first problem of Problem Set 06, without the parts of the WHERE clauses that forbade cycles in the list of schedules. For the second problem, you will create a graphical user interface for creating and testing finite state machines.

For both of these problems, you should use HOFs whenever they improve your code.

(trains-3). Repeat problem 1 from Problem Set 06, without the parts of the WHERE clauses that say "it is not possible to ride forever using the schedules given".

(define adirondack
  (make-schedule
   "Adirondack"
   (list (make-brief-stop (make-train-time 10 20 "A") "Montreal, QC")
         (make-brief-stop (make-train-time  1 25 "P") "Plattsburgh, NY")
         (make-brief-stop (make-train-time  4 45 "P") "Saratoga Springs, NY")
         (make-stop       (make-train-time  5 57 "P")
                          (make-train-time  6 15 "P") "Albany, NY")
         (make-brief-stop (make-train-time  7 15 "P") "Poughkeepsie, NY")
         (make-brief-stop (make-train-time  8 50 "P") "New York, NY"))))

(define adirondack-nb
  (make-schedule
   "Adirondack (northbound)"
   (list (make-brief-stop (make-train-time  8 15 "A") "New York, NY")
         (make-brief-stop (make-train-time  9 45 "A") "Poughkeepsie, NY")
         (make-stop       (make-train-time 10 50 "A")
                          (make-train-time 11 10 "A") "Albany, NY")
         (make-brief-stop (make-train-time 12 02 "P") "Saratoga Springs, NY")
         (make-brief-stop (make-train-time  3 22 "P") "Plattsburgh, NY")
         (make-brief-stop (make-train-time  7 11 "P") "Montreal, QC"))))

(define empire-service
  (make-schedule
   "Empire Service"
   (list (make-brief-stop (make-train-time 12 05 "P") "Albany, NY")
         (make-brief-stop (make-train-time  1 10 "P") "Poughkeepsie, NY")
         (make-brief-stop (make-train-time  2 45 "P") "New York, NY"))))

(define empire-service-nb
  (make-schedule
   "Empire Service (northbound)"
   (list (make-brief-stop (make-train-time  3 15 "P") "New York, NY")
         (make-brief-stop (make-train-time  4 40 "P") "Poughkeepsie, NY")
         (make-brief-stop (make-train-time  5 45 "P") "Albany, NY"))))

(define ethan-allen-express
  (make-schedule
   "Ethan Allen Express"
   (list (make-brief-stop (make-train-time  8 00 "A") "Rutland, VT")
         (make-brief-stop (make-train-time  9 37 "A") "Saratoga Springs, NY")
         (make-stop       (make-train-time 10 50 "A")
                          (make-train-time 11 10 "A") "Albany, NY")
         (make-brief-stop (make-train-time 12 10 "P") "Poughkeepsie, NY")
         (make-brief-stop (make-train-time  1 45 "P") "New York, NY"))))

(define ethan-allen-express-nb
  (make-schedule
   "Ethan Allen Express (northbound)"
   (list (make-brief-stop (make-train-time  3 15 "P") "New York, NY")
         (make-brief-stop (make-train-time  4 40 "P") "Poughkeepsie, NY")
         (make-stop       (make-train-time  5 45 "P")
                          (make-train-time  6 00 "P") "Albany, NY")
         (make-brief-stop (make-train-time  6 50 "P") "Saratoga Springs, NY")
         (make-brief-stop (make-train-time  8 48 "P") "Rutland, VT"))))

(define those-six-trains
  (list adirondack          adirondack-nb
        empire-service      empire-service-nb
        ethan-allen-express ethan-allen-express-nb))

(define those-same-six-trains
  (reverse those-six-trains))

(trains-connect? those-six-trains
                 "Boston, MA" "New York, NY")                       ; => false
(trains-connect? those-six-trains
                 "Plattsburgh, NY" "Rutland, VT")                   ; => true
(trains-connect? those-same-six-trains
                 "Plattsburgh, NY" "Rutland, VT")                   ; => true
(itinerary those-six-trains
           "Plattsburgh, NY" "Rutland, VT")
;;; =>
;;; (list
;;;  (make-schedule
;;;   "Adirondack"
;;;   (list
;;;    (make-brief-stop (make-train-time 1 25 "P") "Plattsburgh, NY")
;;;    (make-brief-stop (make-train-time 4 45 "P") "Saratoga Springs, NY")))
;;;  (make-schedule
;;;   "Ethan Allen Express (northbound)"
;;;   (list
;;;    (make-brief-stop (make-train-time 6 50 "P") "Saratoga Springs, NY")
;;;    (make-brief-stop (make-train-time 8 48 "P") "Rutland, VT"))))

(itinerary those-six-trains
           "Plattsburgh, NY" "Rutland, VT")
;;; => same abbreviated itinerary as above
;;;
;;; There are 636 ways to get from Plattsburgh to Rutland
;;; using those six trains without taking any train twice,
;;; but that's the only way to do it in 443 minutes.

(travel-time those-six-trains
             "Plattsburgh, NY" "Rutland, VT")                        ; => 443

(fsm-3). For this problem, you will deliver a file named fsm-3.rkt that implements a graphical user interface (GUI) for creating and testing finite state machines. That GUI is specified as follows:
- The finite state machine being created, edited, or tested is displayed on a canvas 600 pixels wide and 500 pixels high. The canvas starts out blank (all white).
- The machine's start state is displayed as a red outline circle with radius 20. All other states are displayed as a black outline circle with radius 20. Accepting states are displayed with an inner circle of radius 17 having the same center and color as the outer circle of radius 20. Each state's name is displayed in black at the center of its circle, but names longer than six characters may be truncated to their first six characters when displayed.
- Each state's transitions are displayed as curves connecting its circle to the circle for the destination of the transition. (Those two circles will be the same when there's a transition from a state to itself, but the curve should be clearly visible even in that case.) The destination end of the curve is marked by an open arrowhead. The curve's label, an InputSymbol, is displayed (without quote marks) next to the curve.
- A subset of the machine's states may be selected in one of several ways described below. All of the currently selected states are displayed with a pale blue solid circle of radius 20, concentric with the state's red or black circle. The pale blue solid circle lies beneath all other graphics displayed for a state, so the state's name remains visible even when the state is selected.
- The machine starts out with no states. (The is-machine? function says a machine with no states isn't really a machine. In this specification, we're going to call it a machine anyway.)
- A new state is created by typing "N", followed by the name of the state, followed by the return/enter key "\r". Between the "N" and the "\r", all mouse events are ignored and the canvas changes from white to pale gray (outside of the circles that represent states). When the "\r" is typed, the canvas returns to its normal white color. If there is no start state when the new state is created, then the new state will become the start state. Otherwise the new state is not a start state. New states are not selected, and creating a new state does not affect the currently selected set of states.
  The first state created is centered at canvas coordinates (50,50), the second at (150,50), the third at (250,50), the fourth at (350,50), the fifth at (450,50), and the sixth at (550,50). The seventh through twelfth states are created 100 pixels below those, the thirteenth through eighteenth are another 100 pixels down, the nineteenth through twenty-fourth another 100 pixels down, and the twenty-fifth through thirtieth another 100 pixels down, with the thirtieth state centered at (550,450). After thirty states have been created, that sequence of locations is repeated as many times as necessary.
- A new transition is created by typing "T", followed by typing an InputSymbol (defined as one of the lower-case letters "a" through "z" or one of the digits "0" through "9"), followed by briefly clicking the mouse first within one state's circle and then within a second state's circle. The transition goes from the first state clicked to the second, and is labelled by the InputSymbol. All states become unselected when the "T" is pressed, and all states are still unselected when the entire input sequence is complete.
  Between the "T" and the InputSymbol, all mouse events are ignored and the canvas changes from white to pale gray (outside of the circles that represent states). Between the InputSymbol and the second mouse click, all other kinds of mouse events are ignored, all key events are ignored, and the canvas remains pale gray. When the destination state is clicked, the canvas returns to its normal white color and the new transition is displayed along with the rest of the machine.
  
  If either mouse click that follows the typing of a "T" and an InputSymbol fails to click on a state of the machine, or clicks on two or more states at once, then no new transition is defined and the canvas immediately returns to its normal white color.
- Outside of the special situations described above for sequences of events starting with key events "N" and "T", depressing the mouse button within a state's circle selects that state and unselects all states whose circles do not contain the mouse location. Releasing the mouse button unselects all states. In between those events, the state(s) selected using the mouse can be dragged smoothly around the canvas the same way goofballs were dragged in the screensavers. As a state is dragged to new positions, the curves representing transitions leading out of or into the state are automatically updated to lead out of or into the circle at the state's new positions.
- Typing "A" changes the accepting status of all currently selected states, without changing the status of unselected states. If a selected state was an accepting state when the "A" was typed, it will not be an accepting state afterwards. If a selected state was not an accepting state when the "A" was typed, it will be an accepting state afterwards.
- Typing "S" unselects all states except the start state, and the start state (if there is one) becomes the only selected state.
- Typing an InputSymbol changes the set of selected states to the set of states computed by the next-states function when given the currently selected states and that InputSymbol as arguments.
- Typing "D" deletes all selected states. If the machine's start state is deleted, the next new state becomes the start state.
- Typing "U" unselects all states.
Example: The following scene was produced by
- typing "N", "q", "1", "\r"
- typing "N", "q", "2", "\r"
- typing "N", "q", "3", "\r"
- typing "T", "a", and clicking twice on state q1
- typing "T", "b", and clicking first on state q1 and then on state q2
- typing "T", "c", and clicking first on state q1 and then on state q3
- typing "S" to select the start state q1
- typing "c" to follow the transition to state q3
Here is an example of a finite state machine that accepts all binary numerals congruent to 3 mod 5:

Your fsm-3.rkt file must provide all thirteen functions provided by your fsm-2.rkt file in Problem Set 06, and must also provide the following nine functions:
```
;;; run : PosReal -> World
;;; GIVEN: the number of seconds per tick
;;; EFFECT: runs the GUI, starting with the initial state
;;;     returned by initial-world
;;; RETURNS: the final state of the world
;;; EXAMPLES:
;;;     (run 1)

;;; initial-world : Any -> World
;;; GIVEN: any value (ignored)
;;; RETURNS: the initial world specified for the GUI
;;; EXAMPLE: (initial-world 0)

;;; world-after-key-event : World KeyEvent -> WorldState
;;; GIVEN: a World and a KeyEvent
;;; RETURNS: the World that should follow the given World
;;;     after the given KeyEvent

;;; world-after-mouse-event : World Int Int MouseEvent -> World
;;; GIVEN: a World, the x- and y-coordinates of a mouse event, and the
;;;     mouse event
;;; RETURNS: the world that should follow the given world after the given
;;;     mouse event.

;;; world-machine : World -> ListOfMachineState
;;; GIVEN: a World
;;; RETURNS: the list of machine states being displayed in that world
;;;     (which might not be a machine as defined by is-machine?)
;;; EXAMPLE: (world-machine (initial-world 0)) => empty

;;; world-selected-states : World -> ListOfMachineState
;;; GIVEN: a World
;;; RETURNS: a list of the currently selected machine states

;;; world-with-selected-states : World ListOfMachineState -> World
;;; GIVEN: a world and a list containing some of its machine states
;;; WHERE: the list is a set (contains no duplicates)
;;; RETURNS: a world like the given world but with the given set
;;;     of machine states as its set of selected states
;;; EXAMPLE:
;;;     if q1 and q2 belong to (world-machine world), then
;;;     (world-selected-states
;;;      (world-with-selected-states world (list q1 q2)))
;;;     => (list q1 q2) or (list q2 q1)

;;; world-with-new-state : World String -> World
;;; GIVEN: a World and the name of a new state
;;; WHERE: no state in the world already has that name
;;; RETURNS: the world that should result from typing "N"
;;;     followed by the name of the new state, followed by "\r"
;;; EXAMPLE:
;;;     (world-machine
;;;      (world-with-new-state (initial-world 17) "q0"))
;;;  => (list (make-machine-state "q0" true false empty))

;;; world-with-new-transition :
;;;     World InputSymbol MachineState MachineState -> World
;;; GIVEN: a world, an input symbol, and machine states q1 and q2
;;; WHERE: q1 and q2 belong to (world-machine world),
;;;     and q1 doesn't already have a transition to q2 via the input symbol
;;; RETURNS: the world that should result from adding a transition
;;;     labelled by the given input symbol that takes q1 to q2
```
Hint: The scene+curve function of 2htdp/image is useful when drawing edges of a graph. Open arrowheads can be drawn using line. Do not worry about drawing nicer-looking graphs until you have completed a first draft of your solution.

Last modified: Thu Mar 03 2016